package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/count-good-nodes-in-binary-tree">统计二叉树中好节点的数目(Count Good Nodes in Binary Tree)</a>
 * <p>给你一棵根为 root 的二叉树，请你返回二叉树中好节点的数目。</p>
 * <p>「好节点」X 定义为：从根到该节点 X 所经过的节点中，没有任何节点的值大于 X 的值。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [3,1,4,3,null,1,5]
 *                     <a color='blue'>3</a>
 *                    / \
 *                   1   <a color='blue'>4</a>
 *                  /   / \
 *                 <a color='blue'>3</a>   1   <a color='blue'>5</a>
 *      输出：4
 *      解释：图中蓝色节点为好节点。
 *          根节点 (3) 永远是个好节点。
 *          节点 4 -> (3,4) 是路径中的最大值。
 *          节点 5 -> (3,4,5) 是路径中的最大值。
 *          节点 3 -> (3,1,3) 是路径中的最大值。
 *
 * 示例 2：
 *      输入：root = [3,3,null,4,2]
 *                       <a color='blue'>3</a>
 *                      /
 *                     <a color='blue'>3</a>
 *                    /  \
 *                   <a color='blue'>4</a>    2
 *      输出：3
 *      解释：节点 2 -> (3, 3, 2) 不是好节点，因为 "3" 比它大。
 *
 * 示例 3：
 *      输入：root = [1]
 *      输出：1
 *      解释：根节点是好节点。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>二叉树中节点数目范围是 [1, 10^5] 。</li>
 *     <li>每个节点权值的范围是 [-10^4, 10^4] 。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/13 14:39
 */
public class LC1448CountGoodNodesInBinaryTree_M {

    static class Solution {
        public int goodNodes(TreeNode root) {
            return dfs(root, root.val);
        }

        private int dfs(TreeNode currNode, int maxVal) {
            if (currNode == null) {
                return 0;
            }
            // 判断当前节点是否为好节点；如果是：结果+1，并更新最大值
            int res = 0;
            if (currNode.val >= maxVal) {
                res++;
                maxVal = currNode.val;
            }
            // 判断左右子树好节点的个数
            return res + dfs(currNode.left, maxVal) + dfs(currNode.right, maxVal);
        }
    }
}